There are many situations where it is useful to count the number of consecutive ones or zeros in a binary number starting from the either the left hand side (i.e. starting with the most significant bit (MSB)) or the right hand side (i.e. starting with the least significant bit (LSB)). When counting from the most significant bit, this may be referred to as counting leading ones or zeros (e.g. a binary number 0111 has one leading zero and a binary number 1100 has two leading ones). When counting from the least significant bit this may be referred to as counting trailing ones or zeros (e.g. a binary number 1100 has two trailing zeros and a binary number 1000 has three trailing zeros).
Counting the leading or trailing zeros comprises detecting the first one in the binary number from the MSB or LSB respectively; or in other words, detecting the first transition from a zero to a one from the MSB or LSB. Similarly, counting the leading or trailing ones comprises detecting the first zero in the binary number from the MSB or LSB respectively; or in other words detecting the first transition from a one to a zero from the MSB or LSB.
A leading zero counter (LZC), which counts the number of leading zeros, may, for example, be used for normalization in floating point arithmetic (e.g. floating point addition). It will be appreciated, however, that a trailing zero counter (TZC) which counts the trailing zeros may be used as a leading zero counter, and vice versa, by connecting up the inputs such that the true MSB of the input binary number is connected to the LSB input of the trailing zero counter or the leading zero counter.
The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known trailing or leading zero anticipators.